package com.learn.medium;

import java.util.List;

/**
 * Given the head of a singly linked list,<br>
 * group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.<br>
 *
 * The first node is considered odd, and the second node is even, and so on.<br>
 *
 * Note that the relative order inside both the even and odd groups should remain as it was in the input.<br>
 *
 * You must solve the problem in O(1) extra space complexity and O(n) time complexity.<br>
 */
public class num_328 {
    static ListNode listNode = new ListNode();
    static {
        // listNode = new ListNode(1);
        // listNode.next = new ListNode(2);
        // listNode.next.next = new ListNode(3);
        // listNode.next.next.next = new ListNode(4);
        // listNode.next.next.next.next = new ListNode(5);
    }

    public static void main(String[] args) {
        oddEvenList(listNode);

    }

    public static ListNode oddEvenList(ListNode head) {
        if (head == null || (head.val == 0 && head.next == null)) {
            return head;
        }
        ListNode odd = new ListNode();
        ListNode copyOdd = odd;
        ListNode even = new ListNode();
        ListNode copyEven = even;
        int tag = 1;

        while (head != null) {
            if (tag == 1) {
                odd.next = new ListNode(head.val);
                odd = odd.next;
                tag = 0;
            } else {
                even.next = new ListNode(head.val);
                even = even.next;
                tag = 1;
            }
            head = head.next;
            if (head == null) {
                copyOdd = copyOdd.next;
                copyEven = copyEven.next;
                odd.next = copyEven;
            }
        }
        return copyOdd;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
